#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const LL MOD=1000000000;
const int MAXN=400;
char ch[MAXN];
LL ans[MAXN][MAXN];
LL dp(int l, int r) {
	LL res=ans[l][r];
	if (res>=0) return res;
	if (l==r) return ans[l][r]=1;
//	if ((r-l)%2==1) return 0;
	if (ch[r]!=ch[l]) return ans[l][r]=0;
	res=0;
	for (int i=l+2; i<=r; ++i) {
		if (ch[i]==ch[l]) res=(res+dp(l+1, i-1)*dp(i, r))%MOD;
	}
	return ans[l][r]=res;
}
int main() {
//	freopen("in.txt", "r", stdin);
//	freopen("exploring.in", "r", stdin);
//	freopen("exploring.out", "w", stdout);
	while (cin>>ch) {
		int len=strlen(ch);
		memset(ans, -1, sizeof(ans));
		cout<<dp(0, len-1)<<endl;
	}
	return 0;
}

